1. Field Of The Invention
This invention relates to a system and method for representing and solving complex problems. More specifically, the present invention relates to a system and method for representing and solving constraint satisfaction and optimization problems. Still more specifically, the invention relates to a system and method for representing and solving constraint satisfaction and optimization problems using an integrated combination of operations research and artificial intelligence techniques.
2. Related Art
Constraint satisfaction and optimization problems, in general terms, involve problems where an attempt is made to achieve certain goals, while maintaining the value of specified variables within designated boundaries. Although such problems have been studied for many years, many have long been considered very difficult if not impossible to represent and solve due to their complexity.
With the arrival of computer technology, it became possible to solve many of these previously unsolved problems. This was accomplished by customized computer programs that were developed to solve a specific problem or perhaps a particular class of constraint satisfaction and optimization problems. However, even with the advent of computers, many constraint satisfaction and optimization problems are still considered too difficult to easily and/or accurately represent and solve. One major reason for this relates to the present techniques used to represent and solve these problems.
There are two traditional approaches used to represent a constraint satisfaction and optimization problem. The first is a numerical approach used by mathematicians and those in the field of Operations Research (OR). This approach involves building mathematical models expressed in numerical terms using algebraic formulas or calculus.
The second traditional approach involves representing the problem symbolically. In other words, symbols, mnemonics, rules and predicates are used for expressing operations and operands, rather than mathematical equations. This approach is used by those working in the domain of artificial intelligence (AI), which is a discipline of the computer science field.
The approach that will work best for a particular problem will depend on the specific problem at issue. In general, each approach has advantages and disadvantages. An advantage of the numerical approach is that representation of a problem is concise, and has relatively little ambiguity. Also, there exist efficient procedures for solving some of the problems that can be expressed purely numerically.
A major disadvantage with the numerical approach is that many types of problems cannot be completely represented in the numerical form required by existing methods. When such a problem comes up, mathematicians in OR represent as much of the problem as possible numerically. That which they cannot represent numerically is temporarily ignored. After the represented portion of the problem is solved, the mathematicians ask themselves "what would the solution to the problem be if the previously ignored portions caused the problem to behave one way, or caused it to behave a different way, etc." Thus, the unrepresented portions of the problem cause the overall problem solving process to become one of trial-and-error. Such a process wastes much time and effort.
An advantage of the symbolic approach used in AI is that it is easier to represent certain types of problems which are more easily thought of symbolically (that is, in terms of rules and statements). An example of such a rule might look like "if Bob and Mary are married, schedule them to work on the same day." This type of problem, while easily represented symbolically, would be quite difficult to represent numerically.
The symbolic approach has some disadvantages versus the numerical approach. That is, it is difficult to apply numeric optimization procedures to a model which is stated in non-numeric terms. There are fewer general purpose procedures available for the solution of problems stated in terms of arbitrary predicates and rules.
In summary, the numerical approach more easily allows numerical components of a problem to be represented than the symbolic components, while with the symbolic approach, the symbolic components are more easily represented than the numerical components. Since real-world constraint satisfaction and optimization problems usually contain both "hybrid" approach which allows easy representation of problems having both of these components.
Although a single "hybrid" approach described above would be of great practical value, serious steps have not been taken toward developing a general purpose problem solver which can represent constraint satisfaction and optimization problems having both symbolic and numerical components. In most cases, such a hybrid approach has only been written about at the highest levels of conceptualization; see Simon, H. A., "Two Heads Are Better Than One: The Collaboration Between AI and OR", Interfaces, Pp. 8-15, Jul.-Aug., (1987). While the hybrid approach is still largely theoretical, there are a few examples where it has been implemented. However, these implementations relate only to the representation of specific problems. One example was used in a doctoral dissertation by Robert Donnelly at The University of Delaware (1988). Donnelly represented a problem called Aggregate Planning using a hybrid of numerical and symbolic approaches. This problem involved the scheduling of people, inventory, shifts, etc. As indicated above, the techniques Donnelly used to develop this representation only work for this particular problem. If the problem is changed slightly, the representation will no longer be effective, and a solution will not result.
Another example of implementation of the hybrid approach was reported in an article by Vasant Dhar; see Dhar, et al.. "Integer Programming vs. Expert systems: An Experimental Comparison", Communications of the ACM, Pp. 323-336, Mar. (1990). In this article, a hybrid approach was used to represent a specific employee scheduling problem. Again, this approach was not capable of being used to represent and ultimately solve other types of constraint satisfaction and optimization problems.
Thus, a tool which can easily represent many different types of problems having both numerical and symbolic components would be very useful. However, prior to the development of the present invention, no such general purpose tool has been available.
An example of an attempt to combine numerical and symbolic components is a product developed by mdbs, Inc., called Guru. Guru allows one to employ a spreadsheet environment (numerical component) as an interface to an expert system (symbolic component). However, because the expert system and spreadsheet portions are not homogeneously integrated, and because the product does not make use of OR techniques, it is still difficult, if not impossible, to represent and solve a multitude of constraint satisfaction and optimization problems. (There are commercial attempts to combine OR techniques and spreadsheet environment by providing add-on programs, which can solve linear programming, to commercial spreadsheets. An example of such an attempt is "What's Best" by General Optimization of Chicago, Illinois. These attempts, which are targeted at making the representation of the problem easier, use only numerical (spreadsheet) components. They are also targeted at representing and solving a limited class of problems, such as linear programming problems).
In addition to the difficulties involved with representing a hybrid numerical/symbolic constraint satisfaction and optimization problem, the actual solving of such a problem is also very difficult. Traditionally, once such a problem is represented, an expert analyzes the problem and decides which of a multitude of algorithms is best suited to solve it.
At present, programs exist to assist in solving certain types of problems. These programs are generally neither readily available nor user-friendly. An example of such a program is "Lindo" by Linus Schrage at the University of Chicago (available from Scientific Press, Redwood City, Calif.). Lindo will solve a problem if it is real and linear, and some specific integer programming problems. Lindo cannot solve general integer programming problems. For these problems there are no efficient algorithms. That is, even for the best known algorithms, the solution time grows exponentially with the size of these problems.
If the problem to be solved is non-linear, it becomes even more difficult to find and use a single algorithm. Therefore, it may be desirable to use several different algorithms to completely solve a particular non-linear problem.
Automated analysis of a problem and selection of an appropriate algorithm to effect a solution has been set forth in a dissertation by Jae Sik Lee at the Wharton School of Business (1989). However, once an algorithm has been selected, it is not changed during the solving process. Thus, solving becomes inefficient, and in some cases impossible by this method, since different algorithms may need to be used at various stages of the solving process. This is especially true where the problem itself changes dynamically during the solution process as may occur when the model is refreshed by new sets of values from an on-line data source.
In addition to the difficulty with the selection of an algorithm to effect a solution to a problem, there is also a problem with managing constraint satisfaction and optimization problems which are infeasible. By infeasible, it is meant that the problem has no solution which satisfies every constraint. In the real world, many problems which people attempt to solve turn out to be infeasible. Nonetheless, even when a problem is infeasible, the designer of the problem would often want to have the "best" answer possible, even if there is no absolute solution.
An example of the type of problems which are often infeasible are problems to select stocks for purchase. The goal of this kind of problem might be to buy stocks with a high rate of return and a low risk. Depending upon how "high" and "low" are defined, this problem may have no solution, since there may be no stocks yielding a "high" enough return and having a "low" enough risk. Thus, when people model real problems, they often include constraints which make feasible solutions impossible.
In the field of OR, infeasibility is traditionally handled by having an expert remodel the problem and manually trying various mathematical techniques until a model of the problem can be created which admits a feasible solution. Thus, the approach is to modify the constraints of the problem until the problem becomes feasible. Using the above example, the rate of risk may be increased or the yield decreased until a stock is found to exist which provides a solution to the problem. However, in the business world, the "best" answer (best balanced solution) to the original infeasible problem may nonetheless be of great value. The difficulty is that the mathematical end of OR is very literal in nature, and is traditionally not concerned about partial or "best" answers. Either a feasible solution exists, or the result is deemed worthless. This philosophy and the general techniques used in OR are thus not conducive to solving infeasible problems.
The field of AI does not have the same kind of general techniques permeating through it the way that OR does, since the techniques used have been problem-specific. Thus, with AI, there are few pervading philosophies that would inhibit the search for "best" solutions where no feasible solutions exist. However, for the very reason that there are no traditional techniques or philosophies, it is still very difficult to solve infeasible problems.
In addition to being poorly equipped to handle infeasible problems, the traditional approaches of both AI and OR consider only one goal at a time. For example, consider the above noted problem to find a stock having both a high rate of return and a low risk. This is an example of a problem having two goals. Traditionally, the way to solve such a problem is to concentrate on one goal at a time. Thus, one would either pick a level of risk and compute the stock having the highest rate of return, or pick a level of return and compute the stock having minimum risk. If both goals are not considered simultaneously, it becomes difficult to find an optimal solution of a complex problem (or a best balanced solution if the problem is infeasible). Business problems in particular often create a constant conflict between multiple goals.
Some specialized systems called "Multiple Goal Programming Systems" exist which are designed to solve problems with multiple goals. These systems require that weights be assigned to individual goals either from explicit information, or from direct user input. These systems are usually used as part of linear programming packages, and as such are not complete problem solving systems, nor would they be good for solving non-linear problems. In addition, a substantial amount of user interaction is required in interacting with the system. Consequently, these systems become very inefficient when dealing with large, complex problems.
Thus, what is needed is a robust problem solving tool which can efficiently represent and solve constraint satisfaction and optimization problems having both numerical and symbolic elements, involving both continuous and integer quantities, and involving any number of objectives and constraints, using a variety of problem solving techniques, and which can find an optimal solution to feasible problems or a best balanced solution to infeasible problems. The present invention provides such a tool.